package Algorithms.Dynamic;

import java.util.*;

/**
 * 动态规划算法（最优解问题）
 */
public class Optimize {

    static final List<Task> taskList;


    static {
        taskList = new ArrayList<>();

        taskList.add(new Task().setSalary(5).setStartTime(1).setEndTime(4));

        taskList.add(new Task().setSalary(1).setStartTime(3).setEndTime(5));

        taskList.add(new Task().setSalary(8).setStartTime(0).setEndTime(6));

        taskList.add(new Task().setSalary(4).setStartTime(4).setEndTime(7));

        taskList.add(new Task().setSalary(6).setStartTime(3).setEndTime(8));

        taskList.add(new Task().setSalary(3).setStartTime(5).setEndTime(9));

        taskList.add(new Task().setSalary(2).setStartTime(6).setEndTime(10));

        taskList.add(new Task().setSalary(4).setStartTime(8).setEndTime(11));


    }

    public static void main(String[] args) {

        int[] prev = prev();

        System.out.println(Arrays.toString(prev));

        List<TaskRecord> taskRecordList = calculateOptimizedValue(prev);

        System.out.println(taskRecordList.toString());

        TaskRecord optimizedTask = taskRecordList.get(taskRecordList.size() - 1);

        System.out.println("构成最优解的任务id是："+optimizedTask);

        System.out.println("最优解是（最大工资是）："+optimizedTask.getOptimizedValue(taskList));
    }

    public static List<TaskRecord> calculateOptimizedValue(int[] prev) {
        /**
         * 用于记录各个任务的最优解，任务id从1开始（用空的TaskRecord填充到list的第0号位置）
         * */
        List<TaskRecord> taskOptimizedList = new ArrayList<>();

        TaskRecord empty = new TaskRecord();

        taskOptimizedList.add(empty);

        for (int i = 0; i < taskList.size(); i++) {

            int optimizeThatNotSelectCurrentTask = 0;

            int optimizeThatSelectCurrentTask = 0;

            int taskId = i + 1;

            TaskRecord taskRecord = null;

            if (taskId != 1) {

                //一、不选择第i个任务
                // 1、查询当前任务的上一个任务在最优解记录表中的组成任务id
                taskRecord = taskOptimizedList.get(taskId - 1);

                // 2、并通过其最优解的组成任务id集合，查询出其对应的最优解（工资）
                optimizeThatNotSelectCurrentTask = taskRecord.getOptimizedValue(taskList);

                //二、选择第i个任务
                // 1、从prev[]中查出，与第i个任务时间上不重叠的且在第i个任务之前的最近的一个任务
                TaskRecord selected = taskOptimizedList.get(prev[taskId]);

                // 2、第i个任务的解（工资）+ 第i个任务最近的任务（时间上不重叠的且在第i个任务之前的最近的一个任务）的最优解（工资）= 选择第i个任务的接（累计工资）
                optimizeThatSelectCurrentTask = selected.getOptimizedValue(taskList) + taskList.get(i).getSalary();

                // 3、如果第i个任务的解（工资）和最近任务（时间上不重叠的且在第i个任务之前的最近的一个任务）的最优解（工资）> 第i-1个任务的最优解
                if (optimizeThatSelectCurrentTask > optimizeThatNotSelectCurrentTask) {

                    // 4、那么就将构成最近任务（时间上不重叠的且在第i个任务之前的最近的一个任务）的任务id取出
                    taskRecord = new TaskRecord();
                    taskRecord.getContainsTaskId().addAll(selected.getContainsTaskId());
                    // 5、再将第i个任务的id添加到 最近任务（时间上不重叠的且在第i个任务之前的最近的一个任务）作为第i个任务的最优解
                    taskRecord.getContainsTaskId().add(taskId);
                }
                // 6、如果没有选择当前任务，默认就使用第i-1个任务作为第i个任务的最优解
            } else {
                // 专门为第一个任务而设计的
                taskRecord = new TaskRecord();
                taskRecord.getContainsTaskId().add(taskId);
            }
            //三、将第i个任务最优解所包含的任务id记录下来
            taskOptimizedList.add(taskRecord);

        }

        return taskOptimizedList;

    }


    /**
     * @return index 对应当前是第几个任务（从1开始），index对应的值为当前任务最接近的前一个任务
     */
    public static int[] prev() {

        int[] prev = new int[taskList.size() + 1];

        for (int i = taskList.size() - 1; i >= 0; i--) {

            Task task = taskList.get(i);

            for (int j = i - 1; j >= 0; j--) {

                Task prevTask = taskList.get(j);
                // 第i-1个任务的结束时间 <= 第i个任务的开始时间，说明这两个任务在时间上不重叠
                if (prevTask.getEndTime() <= task.getStartTime()) {

                    prev[i + 1] = j + 1;
                    // 已找到（时间上不重叠的且在第i个任务之前的最近的一个任务）就不继续往下找了，不然找到的任务会被替换
                    break;
                }
            }

        }

        return prev;
    }
}
